#
# @lc app=leetcode.cn id=93 lang=python3
#
# [93] 复原 IP 地址
#

# @lc code=start
def Backtracking(s: str, start: int, deep: int, ans: List, tmp: List) -> None:
    if start >= len(s):
        return
    if deep == 4:
        if s[start] == '0': # 包含前导0
            if start + 1 == len(s): # 最后一个0
                ans.append(".".join(tmp) + ".0")
        else:
            addr_last = s[start::]
            if int(addr_last) <= 255:
                ans.append(".".join(tmp) + "." + addr_last)
    else:
        for i in range(1, 4):
            addr_str = s[start:start + i]
            tmp.append(addr_str)
            if int(addr_str) == 0:
                Backtracking(s, start + i, deep + 1, ans, tmp)
                tmp.pop()
                break
            elif int(addr_str) <= 255:
                Backtracking(s, start + i, deep + 1, ans, tmp)
            tmp.pop()


class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ans = []
        Backtracking(s, 0, 1, ans, [])
        return ans

# @lc code=end
